Oppenheim et al, xe2x80x9cDiscrete-time Signal Processingxe2x80x9d Prentice-Hall, N.J., 1989, pp609-618.
xe2x80x9cNot Applicablexe2x80x9d
xe2x80x9cNot Applicablexe2x80x9d
The usefulness of the Fast Fourier Transform (FFT) is often limited by the computation speed and power consumption. Many researches have been done in order to improve the speed through parallel and pipelined architecture implementation [U.S. Pat. Nos. 5,163,017, 5,034,910, 4,821,224, 4,241,411]. However, all previously known efforts are based on the so called xe2x80x98butterfly structurexe2x80x99 [Oppenheim, 1989] or some variations of it. As the FFT transform size increases, the butterfly size increases, i.e., the locations of input and output data become farther apart. In high speed hardware implementations, this puts a limit on the computation speed since data propagation can not be done at a faster clock rate without added hardware for pipelining. This results in higher complexity circuit with higher power consumption. The current invention does not use the butterfly architecture, and data propagation during the computation is minimized, while the number of computing elements is kept minimal. As a result, the present invention improves FFT computation efficiency over prior arts in terms of speed, hardware complexity and power consumption.
The circuit performs one dimensional (1-D) FFT of size N=N0xc3x97N1xc3x97 . . . xc3x97NMxe2x88x921 where, Nm m=0, 1, . . . Mxe2x88x921, and M are positive numbers, by implementing 1-D FFTs with progressively increasing sizes, N0, N0xc3x97N1, N0xc3x97N1xc3x97N2, . . . , N0xc3x97N1xc3x97 . . . xc3x97NMxe2x88x921, using two dimensional computation devices and methods recursively. First, an 1-D FFT of size N0xc3x97N1 is achieved by a two-dimensional transform device with a twiddle factor multiplier between row and column transform stages, where each transform sizes are N0 and N1, respectively. This is based on the algorithm described by Oppenheim [Oppenheim, pp609-618]. Once 1-D FFT of a size N0xc3x97N1 is computed, one can continue to compute a larger size 1-D FFT using a two-dimensional transform of an increased size (N0xc3x97N1)xc3x97N2 where only column transforms of N2-point DFTs need be further computed following a prior transform of size N0xc3x97N1. New twiddle factors need be multiplied element by element before the new column transform. This process can be continued for a next size ((N0xc3x97N1)xc3x97N2xc3x97N3, and so on, until 1-D FFT of a desired size N0xc3x97N1xc3x97 . . . xc3x97NMxe2x88x921 is achieved.
The complexity of the system is especially minimized if Nm=4 or 2, m=0, 1, . . . Mxe2x88x921, since nontrival multiplications are required only for twiddle factor multiplications. As a result, the number of multiplication nodes in the signal flow is significantly reduced. Since a recursive two-dimensional transform data flow replaces prior art butterfly data flow in the FFT computation, the control circuit for computing butterfly memory address is removed. The combined effect of smaller number of multiplication nodes and simpler control makes the current FFT architecture and algorithm suitable for high-speed operation. Furthermore, by adopting a transpose-less pipelined 2-D transform architecture by Kim (U.S. Pat. No. 5,528,736), a preferred embodiment in the current invention, one output per clock computation throughput rate is achieved.